package com.example.leetcode.sort;

import java.util.Arrays;

public class HeapSort {
    /**
     * 从10亿个数中找出最小的或最大的10个数
     * 思路：找出最小的10个数
     * 采用大顶堆。
     * S1: 首先构建长度为10的大顶堆;
     * S2: 不断地从10亿个数据中读取,
     * 若大于等于顶元素,则丢弃;
     * 若小于顶元素,则替换顶元素,并调整堆adjustHeap。
     */
    public static int[] findMin10Nums(int[] arr) {
        if (arr == null || arr.length < 10) return Arrays.copyOf(arr, arr.length);
        //构建长度为10的大顶堆
        int[] res = Arrays.copyOf(arr, 10);
        int notLeaf = res.length / 2 - 1;
        while (notLeaf >= 0) adjustHeapForMaxTop(res, notLeaf--, res.length);
        //遍历读取每一个数值
        for (int j = 10; j < arr.length; j++) {
            if (arr[j] >= res[0]) continue;//大于顶元素(最大值)
            res[0] = arr[j];
            adjustHeapForMaxTop(res, 0, res.length);
        }
        return res;
    }

    /**
     * 与寻找最小10个数对应
     */
    public static int[] findMax10Nums(int[] arr) {
        if (arr == null || arr.length < 10) return Arrays.copyOf(arr, arr.length);
        //构建长度为10的大顶堆
        int[] res = Arrays.copyOf(arr, 10);
        int notLeaf = res.length / 2 - 1;
        while (notLeaf >= 0) adjustHeapForMinTop(res, notLeaf--, res.length);
        //遍历读取每一个数值
        for (int j = 10; j < arr.length; j++) {
            if (arr[j] <= res[0]) continue;//大于顶元素(最大值)
            res[0] = arr[j];
            adjustHeapForMinTop(res, 0, res.length);
        }
        return res;
    }

    //调整堆--复用堆排的adjustHeap方法(大顶堆)
    public static void adjustHeapForMaxTop(int[] arr, int root, int len) {
        adjustHeapMaxTop(arr, root, len);
    }

    //调整堆--复用堆排的adjustHeap方法(小顶堆)
    public static void adjustHeapForMinTop(int[] arr, int root, int len) {
        adjustHeapMinTop(arr, root, len);
    }

    /**
     * 使用场景及功能:顶节点值发生改变,不一定大于子节点,找到该顶节点值合适的位置,置入即可;
     * 步骤：
     * S1: 比较左右子节点,找到较大值;
     * S2: 将较大值填入root位置,并更新root值和index值;
     * S3: while循环执行S1、S2,直到遇到叶子节点(即左子节点下标大于等于len);
     * S4: 记得最后将rootVal设置到root位置上。
     */
    public static void adjustHeapMaxTop(int[] arr, int root, int len) {
        int index = root * 2 + 1;
        if (index >= len) return;
        int rootVal = arr[root];//根值
        while (index < len) {
            //找出左右子节点的最大值(避免交换两次)
            if (index + 1 < len && arr[index + 1] > arr[index]) index++;
            if (rootVal >= arr[index]) break;//根节点值大于等于子节点值,结束
            arr[root] = arr[index];//利用swap交换root和index也可以,不过有点冗余,index位置可能会多次覆盖
            root = index;
            index = index * 2 + 1;
        }
        arr[root] = rootVal;//若while循环中调用swap,则该操作可省略
    }

    /**
     * 小顶堆
     */
    public static void adjustHeapMinTop(int[] arr, int root, int len) {
        int index = root * 2 + 1;
        if (index >= len) return;
        int rootVal = arr[root];//根值
        while (index < len) {
            //找出左右子节点的最大值(避免交换两次)
            if (index + 1 < len && arr[index + 1] < arr[index]) index++;
            if (rootVal <= arr[index]) break;//根节点值大于等于子节点值,结束
            arr[root] = arr[index];//利用swap交换root和index也可以,不过有点冗余,index位置可能会多次覆盖
            root = index;
            index = index * 2 + 1;
        }
        arr[root] = rootVal;//若while循环中调用swap,则该操作可省略
    }

    public static void main(String[] args) {
        int[] arr = {-2, 100, 9, -8, 7, 6, 11, 5, 4, 3, 2, 1, 32, 4, 56, 67, 44, 23, 54, 34, 23, 234, 65, 34, 1, 0, 5, 0, 6, -23, 1004, 1024, 8989};
        int[] min10Nums = findMin10Nums(arr);
        System.out.println("最小的10个数:" + Arrays.toString(min10Nums));
        int[] max10Nums = findMax10Nums(arr);
        System.out.println("最大的10个数:" + Arrays.toString(max10Nums));
    }

}
